package com.ai.zuochengyun.phase01.class02;

public class Code02_EvenTimesOddTimes {

    public static void main(String[] args) {

        int[] arr = new int[6];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 2;
        arr[3] = 3;
        arr[4] = 3;
        arr[5] = 4;

        findTwoNumOnlyExistsOneTimes(arr);
    }

    private static void findTwoNumOnlyExistsOneTimes(int[] arr) {
        int xor = 0;
        for (int num : arr) {
            xor ^= num;
        }

        // 获取最右侧的1
        int rightOne = xor & (~xor + 1);

        // xor表示最后两个出现了1次的数异或之后的结果
        // 那么可以得出如下结论：
        // 1、xor不为0
        // 2、通过xor不为0，就一定能获取到二进制位上最右侧的1的位置
        // 3、那么既然这个位置为1，那么两个数在这个位置上肯定是一个为1，一个为0
        // 4、那么就可以将所有的数分成两类，一类是在该位置上为1的数，一类是在该位置上为0的数
        int onlyOne = 0;
        for (int num : arr) {
            // 只与上该位置上为1的数
            if ((num & rightOne) != 0) {
                onlyOne ^= num;
            }
        }
        int otherOne = xor ^ onlyOne;
        System.out.println(onlyOne + "和" + otherOne);
    }
}
